/**
 *  01背包
 *
 * 描述
 * 已知一个背包最多能容纳体积之和为v的物品
 * 现有 n 个物品，第 i 个物品的体积为 vi , 重量为 wi
 * 求当前背包最多能装多大重量的物品?
 *
 * 数据范围：
 * 1≤v≤1000 ，
 * 1≤n≤1000 ，
 * 1≤vi≤1000 ，
 * 1≤wi≤1000
 *
 * 进阶 ：
 * O(n⋅v)
 */

/**
 * 使用动态规划
 * 1. 状态表⽰：
 * dp[i][j] 表⽰从前 i 个物品中挑选,总体积不超过 j 的情况下,最⼤重量是多少
 *
 * 2. 状态转移⽅程：
 * 根据「最后⼀步」的状况,来分情况讨论:
 * i.  不选第 i 个物品: 相当于就是去前 i - 1 个物品中挑选,并且总体积不超过 j. 此时 dp[i][j] = dp[i - 1][j];
 * ii. 选择 i 个物品: 那么我就只能去前 i - 1 个物品中, 挑选总体积不超过 j - vw[i][0]的物品.
 * 此时 dp[i][j] = dp[i - 1][j - vw[i][0]] + vw[i][1], 但是这种状态不⼀定存在, 因此需要特判⼀下.
 *
 * 综上, 状态转移⽅程为: dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - vw[i][0]] + vw[i][1])
 * 时间复杂度 : O(n * v)
 * 空间复杂度 : O(n * v)
 */

public class Main {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算01背包问题的结果
     * @param v int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    public int knapsack (int v, int n, int[][] vw) {

        // 这里为下面的多开辟一个空间, 防止数组越界
        int[][] dp = new int[n + 1][v + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= v; j++) {

                if (j < vw[i - 1][0]) {

                    // 要是这个位置的 体积直接大于 j, 那么这个位置就选不了了
                    dp[i][j] = dp[i - 1][j];
                } else {

                    // 选与不远改位置, 看最后的结果
                    dp[i][j] = Math.max(dp[i - 1][j],
                            dp[i - 1][j - vw[i - 1][0]] + vw[i - 1][1]);
                }
            }
        }

        // 返回结果
        return dp[n][v];
    }

    // 进行空间优化
    public int knapsack2 (int V, int n, int[][] vw) {
        int[] dp = new int[1010];

        for(int i = 0; i < n; i++) {

            // 因为后面的是依赖前面的数, 所以我们的第二层循环要从后向前面遍历
            for(int j = V; j >= vw[i][0]; j--) {

                dp[j] = Math.max(dp[j], dp[j - vw[i][0]] + vw[i][1]);
            }
        }
        return dp[V];
    }
}